//https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/

class Solution {
public:
    bool Find(TreeNode* root, TreeNode* x)
    {
        if (root == nullptr)
            return false;

        if (root == x)
            return true;

        return Find(root->left, x) || Find(root->right, x);
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == nullptr)
            return nullptr;

        if (root == p || root == q)
            return root;

        //判断p和q是否同位于左子树或同位于右子树 或者分别在左右子树
        bool pInLeft, pInRight, qInLeft, qInRight;
        pInLeft = Find(root->left, p);
        pInRight = !pInLeft;

        qInLeft = Find(root->left, q);
        qInRight = !qInLeft;

        //都位于左树
        if (pInLeft && qInLeft)
        {
            return lowestCommonAncestor(root->left, p, q);
        }

        //都位于右树
        else if (pInRight && qInRight)
        {
            return lowestCommonAncestor(root->right, p, q);
        }

        else
        {
            return root;
        }
    }
};